| Property | Binary Search Tree | Hash Table |
|---|---|---|
| Ordering | Maintains keys in sorted order. | Keys are unordered. |
| Time Complexity (Avg) | \(O(\log n)\) | \(O(1)\) |
| Time Complexity (Worst) | \(O(n)\) (unbalanced) | \(O(n)\) (all keys collide) |
| Range Queries | Efficient | Inefficient (requires full scan) |
| Space Complexity | \(O(n)\) | \(O(n+m)\) |
| Performance Guarantees | Predictable (with balancing) | Average-case, not guaranteed |
Hover over a row in the table to see a detailed explanation of that property.
BSTs inherently keep elements sorted. This allows for operations like in-order traversal to retrieve all elements in ascending order.
Hash Tables place elements based on their hash, which scrambles any natural order. There's no efficient way to retrieve elements in a sorted manner.
BSTs achieve \(O(\log n)\) for search, insert, and delete because they halve the search space at each step, assuming the tree is reasonably balanced.
Hash Tables offer \(O(1)\) average time because the hash function directly computes the location of an element, requiring just one lookup (plus a short walk if collisions occur).
Both structures can degrade to \(O(n)\). For a BST, this happens if it becomes a long, skewed chain (like a linked list). Self-balancing trees like AVL prevent this.
For a Hash Table, this happens if a poor hash function causes all keys to map to the same slot, forcing a linear search through a long chain or probe sequence.
Finding all elements between \(k_1\) and \(k_2\) is very efficient in a BST due to its sorted nature. We can perform a modified traversal that only visits nodes within the range.
A Hash Table must check every single element in the table to see if it falls within the range, making it highly inefficient for this task.
A BST requires space proportional to the number of nodes, \(n\), storing the key and pointers.
A Hash Table requires space for its backing array of size \(m\) plus the \(n\) keys stored. To keep the load factor low, \(m\) is often larger than \(n\).
A balanced BST (like an AVL tree) offers a strong guarantee: operations will never be worse than \(O(\log n)\).
A Hash Table's \(O(1)\) is an average-case expectation. While highly likely, it's not a hard guarantee; worst-case performance is possible, though rare with a good hash function.